We describe algorithmic results for two crucial aspects of allocatingresources on computational hardware devices with partial reconfigurability. Byusing methods from the field of computational geometry, we derive a method thatallows correct maintainance of free and occupied space of a set of nrectangular modules in optimal time Theta(n log n); previous approaches neededa time of O(n^2) for correct results and O(n) for heuristic results. We alsoshow that finding an optimal feasible communication-conscious placement (whichminimizes the total weighted Manhattan distance between the new module andexisting demand points) can be computed in Theta(n log n). Both resultingalgorithms are practically easy to implement and show convincing experimentalbehavior.
展开▼
